package DP;

/**
 * @author 曹见朋
 * @create 2024-06-11-23:13
 */
public class Main63 {
    // TODO 63. 不同路径 II
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }

        for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
            dp[0][j] = 1;
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                System.out.print(" " + dp[i][j]);
                if(j == n - 1){
                    System.out.println();
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] obstacleGrid = new int[][]{{0,0,0},{0,1,0},{0,0,0}};
        int result = uniquePathsWithObstacles(obstacleGrid);
        System.out.println();
        System.out.println(result);
    }
}
